package backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SumasParciales {
	
	static Set<List<Integer>> toReturn;
	
	public static void sumasParciales(int n){
		 int[] a = new int[n];
		 for(int i=0; i<n;i++)
			 a[i] = 0;
		 
		 sumasParciales(a,1);	
	 
  }
	
	
	public static int suma(int[] v){
		int total=0;
		for(int i :v)
			total+=i;
		return total;
	}
	
	public static void imprimir(int[] v){
		System.out.print("(");
		for(int i :v)
		if(i!=0) System.out.print(i+",");
		System.out.print(")");
	}

  public static void sumasParciales(int[] v, int n) {
	 
     int N = v.length;
      if (suma(v) == N) {
    	//  imprimir(v);
    	  List <Integer> l = new ArrayList<Integer>();
    	  for(int i:v)
    		  if(i!=0) l.add(i);
          toReturn.add(l);
    	  return;
      }
      else {
          for (int i = n; i <= N; i++) {
        	  if((suma(v)+i)<=N) {
            	 v[i-1]=i;
            	 sumasParciales(v,n+1);
             }
             v[i-1]=0;
          }
      }
  }  

	
	public static void main(String[] args){
		toReturn = new HashSet<List<Integer>>();
		
		sumasParciales(8);
		
		for(List<Integer> l:toReturn )
		{
			System.out.print("(");
			for(Integer i: l){
				System.out.print(i);
				if (!l.get(l.size()-1).equals(i)) System.out.print(",");
			}
			System.out.println(")");
		}
	}
}
